Search Results

Documents authored by Göös, Mika

Document
DOI: 10.4230/LIPIcs.ITCS.2024.50
One-Way Functions vs. TFNP: Simpler and Improved

Authors: Lukáš Folwarczný, Mika Göös, Pavel Hubáček, Gilbert Maystre, and Weiqiang Yuan

Published in: LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024)

Abstract
Simon (1998) proved that it is impossible to construct collision-resistant hash functions from one-way functions using a black-box reduction. It is conjectured more generally that one-way functions do not imply, via a black-box reduction, the hardness of any total NP search problem (collision-resistant hash functions being just one such example). We make progress towards this conjecture by ruling out a large class of "single-query" reductions. In particular, we improve over the prior work of Hubáček et al. (2020) in two ways: our result is established via a novel simpler combinatorial technique and applies to a broader class of semi black-box reductions.
Cite as

Lukáš Folwarczný, Mika Göös, Pavel Hubáček, Gilbert Maystre, and Weiqiang Yuan. One-Way Functions vs. TFNP: Simpler and Improved. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 50:1-50:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{folwarczny_et_al:LIPIcs.ITCS.2024.50,
  author =	{Folwarczn\'{y}, Luk\'{a}\v{s} and G\"{o}\"{o}s, Mika and Hub\'{a}\v{c}ek, Pavel and Maystre, Gilbert and Yuan, Weiqiang},
  title =	{{One-Way Functions vs. TFNP: Simpler and Improved}},
  booktitle =	{15th Innovations in Theoretical Computer Science Conference (ITCS 2024)},
  pages =	{50:1--50:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-309-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{287},
  editor =	{Guruswami, Venkatesan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2024.50},
  URN =		{urn:nbn:de:0030-drops-195788},
  doi =		{10.4230/LIPIcs.ITCS.2024.50},
  annote =	{Keywords: TFNP, One-Way Functions, Oracle, Separation, Black-Box}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2023.51
Depth-3 Circuits for Inner Product

Authors: Mika Göös, Ziyi Guan, and Tiberiu Mosnoi

Published in: LIPIcs, Volume 272, 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)

Abstract
What is the Σ₃²-circuit complexity (depth 3, bottom-fanin 2) of the 2n-bit inner product function? The complexity is known to be exponential 2^{α_n n} for some α_n = Ω(1). We show that the limiting constant α := lim sup α_n satisfies 0.847... ≤ α ≤ 0.965... . Determining α is one of the seemingly-simplest open problems about depth-3 circuits. The question was recently raised by Golovnev, Kulikov, and Williams (ITCS 2021) and Frankl, Gryaznov, and Talebanfard (ITCS 2022), who observed that α ∈ [0.5,1]. To obtain our improved bounds, we analyse a covering LP that captures the Σ₃²-complexity up to polynomial factors. In particular, our lower bound is proved by constructing a feasible solution to the dual LP.
Cite as

Mika Göös, Ziyi Guan, and Tiberiu Mosnoi. Depth-3 Circuits for Inner Product. In 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 272, pp. 51:1-51:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{goos_et_al:LIPIcs.MFCS.2023.51,
  author =	{G\"{o}\"{o}s, Mika and Guan, Ziyi and Mosnoi, Tiberiu},
  title =	{{Depth-3 Circuits for Inner Product}},
  booktitle =	{48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)},
  pages =	{51:1--51:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-292-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{272},
  editor =	{Leroux, J\'{e}r\^{o}me and Lombardy, Sylvain and Peleg, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2023.51},
  URN =		{urn:nbn:de:0030-drops-185856},
  doi =		{10.4230/LIPIcs.MFCS.2023.51},
  annote =	{Keywords: Circuit complexity, inner product}
}
Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2022.19
Communication Complexity of Collision

Authors: Mika Göös and Siddhartha Jain

Published in: LIPIcs, Volume 245, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)

Abstract
The Collision problem is to decide whether a given list of numbers (x_1,…,x_n) ∈ [n]ⁿ is 1-to-1 or 2-to-1 when promised one of them is the case. We show an n^Ω(1) randomised communication lower bound for the natural two-party version of Collision where Alice holds the first half of the bits of each x_i and Bob holds the second half. As an application, we also show a similar lower bound for a weak bit-pigeonhole search problem, which answers a question of Itsykson and Riazanov (CCC 2021).
Cite as

Mika Göös and Siddhartha Jain. Communication Complexity of Collision. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 245, pp. 19:1-19:9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{goos_et_al:LIPIcs.APPROX/RANDOM.2022.19,
  author =	{G\"{o}\"{o}s, Mika and Jain, Siddhartha},
  title =	{{Communication Complexity of Collision}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)},
  pages =	{19:1--19:9},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-249-5},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{245},
  editor =	{Chakrabarti, Amit and Swamy, Chaitanya},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2022.19},
  URN =		{urn:nbn:de:0030-drops-171415},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2022.19},
  annote =	{Keywords: Collision, Communication complexity, Lifting}
}
Document
DOI: 10.4230/LIPIcs.CCC.2022.33
Further Collapses in TFNP

Authors: Mika Göös, Alexandros Hollender, Siddhartha Jain, Gilbert Maystre, William Pires, Robert Robere, and Ran Tao

Published in: LIPIcs, Volume 234, 37th Computational Complexity Conference (CCC 2022)

Abstract
We show EOPL = PLS ∩ PPAD. Here the class EOPL consists of all total search problems that reduce to the End-of-Potential-Line problem, which was introduced in the works by Hubáček and Yogev (SICOMP 2020) and Fearnley et al. (JCSS 2020). In particular, our result yields a new simpler proof of the breakthrough collapse CLS = PLS ∩ PPAD by Fearnley et al. (STOC 2021). We also prove a companion result SOPL = PLS ∩ PPADS, where SOPL is the class associated with the Sink-of-Potential-Line problem.
Cite as

Mika Göös, Alexandros Hollender, Siddhartha Jain, Gilbert Maystre, William Pires, Robert Robere, and Ran Tao. Further Collapses in TFNP. In 37th Computational Complexity Conference (CCC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 234, pp. 33:1-33:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{goos_et_al:LIPIcs.CCC.2022.33,
  author =	{G\"{o}\"{o}s, Mika and Hollender, Alexandros and Jain, Siddhartha and Maystre, Gilbert and Pires, William and Robere, Robert and Tao, Ran},
  title =	{{Further Collapses in TFNP}},
  booktitle =	{37th Computational Complexity Conference (CCC 2022)},
  pages =	{33:1--33:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-241-9},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{234},
  editor =	{Lovett, Shachar},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2022.33},
  URN =		{urn:nbn:de:0030-drops-165954},
  doi =		{10.4230/LIPIcs.CCC.2022.33},
  annote =	{Keywords: TFNP, PPAD, PLS, EOPL}
}
Document
Track B: Automata, Logic, Semantics, and Theory of Programming
DOI: 10.4230/LIPIcs.ICALP.2022.126
Lower Bounds for Unambiguous Automata via Communication Complexity

Authors: Mika Göös, Stefan Kiefer, and Weiqiang Yuan

Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)

Abstract
We use results from communication complexity, both new and old ones, to prove lower bounds for unambiguous finite automata (UFAs). We show three results. 1) Complement: There is a language L recognised by an n-state UFA such that the complement language ̅L requires NFAs with n^Ω̃(log n) states. This improves on a lower bound by Raskin. 2) Union: There are languages L₁, L₂ recognised by n-state UFAs such that the union L₁∪L₂ requires UFAs with n^Ω̃(log n) states. 3) Separation: There is a language L such that both L and ̅L are recognised by n-state NFAs but such that L requires UFAs with n^Ω(log n) states. This refutes a conjecture by Colcombet.
Cite as

Mika Göös, Stefan Kiefer, and Weiqiang Yuan. Lower Bounds for Unambiguous Automata via Communication Complexity. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 126:1-126:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{goos_et_al:LIPIcs.ICALP.2022.126,
  author =	{G\"{o}\"{o}s, Mika and Kiefer, Stefan and Yuan, Weiqiang},
  title =	{{Lower Bounds for Unambiguous Automata via Communication Complexity}},
  booktitle =	{49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)},
  pages =	{126:1--126:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-235-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{229},
  editor =	{Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.126},
  URN =		{urn:nbn:de:0030-drops-164679},
  doi =		{10.4230/LIPIcs.ICALP.2022.126},
  annote =	{Keywords: Unambiguous automata, communication complexity}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2022.69
On Semi-Algebraic Proofs and Algorithms

Authors: Noah Fleming, Mika Göös, Stefan Grosser, and Robert Robere

Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)

Abstract
We give a new characterization of the Sherali-Adams proof system, showing that there is a degree-d Sherali-Adams refutation of an unsatisfiable CNF formula C if and only if there is an ε > 0 and a degree-d conical junta J such that viol_C(x) - ε = J, where viol_C(x) counts the number of falsified clauses of C on an input x. Using this result we show that the linear separation complexity, a complexity measure recently studied by Hrubeš (and independently by de Oliveira Oliveira and Pudlák under the name of weak monotone linear programming gates), monotone feasibly interpolates Sherali-Adams proofs. We then investigate separation results for viol_C(x) - ε. In particular, we give a family of unsatisfiable CNF formulas C which have polynomial-size and small-width resolution proofs, but for which any representation of viol_C(x) - 1 by a conical junta requires degree Ω(n); this resolves an open question of Filmus, Mahajan, Sood, and Vinyals. Since Sherali-Adams can simulate resolution, this separates the non-negative degree of viol_C(x) - 1 and viol_C(x) - ε for arbitrarily small ε > 0. Finally, by applying lifting theorems, we translate this lower bound into new separation results between extension complexity and monotone circuit complexity.
Cite as

Noah Fleming, Mika Göös, Stefan Grosser, and Robert Robere. On Semi-Algebraic Proofs and Algorithms. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 69:1-69:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{fleming_et_al:LIPIcs.ITCS.2022.69,
  author =	{Fleming, Noah and G\"{o}\"{o}s, Mika and Grosser, Stefan and Robere, Robert},
  title =	{{On Semi-Algebraic Proofs and Algorithms}},
  booktitle =	{13th Innovations in Theoretical Computer Science Conference (ITCS 2022)},
  pages =	{69:1--69:25},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-217-4},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{215},
  editor =	{Braverman, Mark},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.69},
  URN =		{urn:nbn:de:0030-drops-156658},
  doi =		{10.4230/LIPIcs.ITCS.2022.69},
  annote =	{Keywords: Proof Complexity, Extended Formulations, Circuit Complexity, Sherali-Adams}
}
Document
DOI: 10.4230/LIPIcs.CCC.2021.6
On the Power and Limitations of Branch and Cut

Authors: Noah Fleming, Mika Göös, Russell Impagliazzo, Toniann Pitassi, Robert Robere, Li-Yang Tan, and Avi Wigderson

Published in: LIPIcs, Volume 200, 36th Computational Complexity Conference (CCC 2021)

Abstract
The Stabbing Planes proof system [Paul Beame et al., 2018] was introduced to model the reasoning carried out in practical mixed integer programming solvers. As a proof system, it is powerful enough to simulate Cutting Planes and to refute the Tseitin formulas - certain unsatisfiable systems of linear equations od 2 - which are canonical hard examples for many algebraic proof systems. In a recent (and surprising) result, Dadush and Tiwari [Daniel Dadush and Samarth Tiwari, 2020] showed that these short refutations of the Tseitin formulas could be translated into quasi-polynomial size and depth Cutting Planes proofs, refuting a long-standing conjecture. This translation raises several interesting questions. First, whether all Stabbing Planes proofs can be efficiently simulated by Cutting Planes. This would allow for the substantial analysis done on the Cutting Planes system to be lifted to practical mixed integer programming solvers. Second, whether the quasi-polynomial depth of these proofs is inherent to Cutting Planes. In this paper we make progress towards answering both of these questions. First, we show that any Stabbing Planes proof with bounded coefficients (SP*) can be translated into Cutting Planes. As a consequence of the known lower bounds for Cutting Planes, this establishes the first exponential lower bounds on SP*. Using this translation, we extend the result of Dadush and Tiwari to show that Cutting Planes has short refutations of any unsatisfiable system of linear equations over a finite field. Like the Cutting Planes proofs of Dadush and Tiwari, our refutations also incur a quasi-polynomial blow-up in depth, and we conjecture that this is inherent. As a step towards this conjecture, we develop a new geometric technique for proving lower bounds on the depth of Cutting Planes proofs. This allows us to establish the first lower bounds on the depth of Semantic Cutting Planes proofs of the Tseitin formulas.
Cite as

Noah Fleming, Mika Göös, Russell Impagliazzo, Toniann Pitassi, Robert Robere, Li-Yang Tan, and Avi Wigderson. On the Power and Limitations of Branch and Cut. In 36th Computational Complexity Conference (CCC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 200, pp. 6:1-6:30, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{fleming_et_al:LIPIcs.CCC.2021.6,
  author =	{Fleming, Noah and G\"{o}\"{o}s, Mika and Impagliazzo, Russell and Pitassi, Toniann and Robere, Robert and Tan, Li-Yang and Wigderson, Avi},
  title =	{{On the Power and Limitations of Branch and Cut}},
  booktitle =	{36th Computational Complexity Conference (CCC 2021)},
  pages =	{6:1--6:30},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-193-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{200},
  editor =	{Kabanets, Valentine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2021.6},
  URN =		{urn:nbn:de:0030-drops-142809},
  doi =		{10.4230/LIPIcs.CCC.2021.6},
  annote =	{Keywords: Proof Complexity, Integer Programming, Cutting Planes, Branch and Cut, Stabbing Planes}
}
Document
DOI: 10.4230/LIPIcs.CCC.2021.18
A Majority Lemma for Randomised Query Complexity

Authors: Mika Göös and Gilbert Maystre

Published in: LIPIcs, Volume 200, 36th Computational Complexity Conference (CCC 2021)

Abstract
We show that computing the majority of n copies of a boolean function g has randomised query complexity R(Maj∘gⁿ) = Θ(n⋅R ̅_{1/n}(g)). In fact, we show that to obtain a similar result for any composed function f∘gⁿ, it suffices to prove a sufficiently strong form of the result only in the special case g = GapOr.
Cite as

Mika Göös and Gilbert Maystre. A Majority Lemma for Randomised Query Complexity. In 36th Computational Complexity Conference (CCC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 200, pp. 18:1-18:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{goos_et_al:LIPIcs.CCC.2021.18,
  author =	{G\"{o}\"{o}s, Mika and Maystre, Gilbert},
  title =	{{A Majority Lemma for Randomised Query Complexity}},
  booktitle =	{36th Computational Complexity Conference (CCC 2021)},
  pages =	{18:1--18:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-193-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{200},
  editor =	{Kabanets, Valentine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2021.18},
  URN =		{urn:nbn:de:0030-drops-142922},
  doi =		{10.4230/LIPIcs.CCC.2021.18},
  annote =	{Keywords: Query Complexity, Composition, Majority}
}
Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2020.28
When Is Amplification Necessary for Composition in Randomized Query Complexity?

Authors: Shalev Ben-David, Mika Göös, Robin Kothari, and Thomas Watson

Published in: LIPIcs, Volume 176, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)

Abstract
Suppose we have randomized decision trees for an outer function f and an inner function g. The natural approach for obtaining a randomized decision tree for the composed function (f∘ gⁿ)(x¹,…,xⁿ) = f(g(x¹),…,g(xⁿ)) involves amplifying the success probability of the decision tree for g, so that a union bound can be used to bound the error probability over all the coordinates. The amplification introduces a logarithmic factor cost overhead. We study the question: When is this log factor necessary? We show that when the outer function is parity or majority, the log factor can be necessary, even for models that are more powerful than plain randomized decision trees. Our results are related to, but qualitatively strengthen in various ways, known results about decision trees with noisy inputs.
Cite as

Shalev Ben-David, Mika Göös, Robin Kothari, and Thomas Watson. When Is Amplification Necessary for Composition in Randomized Query Complexity?. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 176, pp. 28:1-28:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{bendavid_et_al:LIPIcs.APPROX/RANDOM.2020.28,
  author =	{Ben-David, Shalev and G\"{o}\"{o}s, Mika and Kothari, Robin and Watson, Thomas},
  title =	{{When Is Amplification Necessary for Composition in Randomized Query Complexity?}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)},
  pages =	{28:1--28:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-164-1},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{176},
  editor =	{Byrka, Jaros{\l}aw and Meka, Raghu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2020.28},
  URN =		{urn:nbn:de:0030-drops-126316},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2020.28},
  annote =	{Keywords: Amplification, composition, query complexity}
}
Document
DOI: 10.4230/LIPIcs.CCC.2020.19
On the Complexity of Modulo-q Arguments and the Chevalley - Warning Theorem

Authors: Mika Göös, Pritish Kamath, Katerina Sotiraki, and Manolis Zampetakis

Published in: LIPIcs, Volume 169, 35th Computational Complexity Conference (CCC 2020)

Abstract
We study the search problem class PPA_q defined as a modulo-q analog of the well-known polynomial parity argument class PPA introduced by Papadimitriou (JCSS 1994). Our first result shows that this class can be characterized in terms of PPA_p for prime p. Our main result is to establish that an explicit version of a search problem associated to the Chevalley - Warning theorem is complete for PPA_p for prime p. This problem is natural in that it does not explicitly involve circuits as part of the input. It is the first such complete problem for PPA_p when p ≥ 3. Finally we discuss connections between Chevalley-Warning theorem and the well-studied short integer solution problem and survey the structural properties of PPA_q.
Cite as

Mika Göös, Pritish Kamath, Katerina Sotiraki, and Manolis Zampetakis. On the Complexity of Modulo-q Arguments and the Chevalley - Warning Theorem. In 35th Computational Complexity Conference (CCC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 169, pp. 19:1-19:42, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{goos_et_al:LIPIcs.CCC.2020.19,
  author =	{G\"{o}\"{o}s, Mika and Kamath, Pritish and Sotiraki, Katerina and Zampetakis, Manolis},
  title =	{{On the Complexity of Modulo-q Arguments and the Chevalley - Warning Theorem}},
  booktitle =	{35th Computational Complexity Conference (CCC 2020)},
  pages =	{19:1--19:42},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-156-6},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{169},
  editor =	{Saraf, Shubhangi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2020.19},
  URN =		{urn:nbn:de:0030-drops-125712},
  doi =		{10.4230/LIPIcs.CCC.2020.19},
  annote =	{Keywords: Total NP Search Problems, Modulo-q arguments, Chevalley - Warning Theorem}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2020.9
The Power of Many Samples in Query Complexity

Authors: Andrew Bassilakis, Andrew Drucker, Mika Göös, Lunjia Hu, Weiyun Ma, and Li-Yang Tan

Published in: LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)

Abstract
The randomized query complexity 𝖱(f) of a boolean function f: {0,1}ⁿ → {0,1} is famously characterized (via Yao’s minimax) by the least number of queries needed to distinguish a distribution 𝒟₀ over 0-inputs from a distribution 𝒟₁ over 1-inputs, maximized over all pairs (𝒟₀,𝒟₁). We ask: Does this task become easier if we allow query access to infinitely many samples from either 𝒟₀ or 𝒟₁? We show the answer is no: There exists a hard pair (𝒟₀,𝒟₁) such that distinguishing 𝒟₀^∞ from 𝒟₁^∞ requires Θ(𝖱(f)) many queries. As an application, we show that for any composed function f∘g we have 𝖱(f∘g) ≥ Ω(fbs(f)𝖱(g)) where fbs denotes fractional block sensitivity.
Cite as

Andrew Bassilakis, Andrew Drucker, Mika Göös, Lunjia Hu, Weiyun Ma, and Li-Yang Tan. The Power of Many Samples in Query Complexity. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 9:1-9:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{bassilakis_et_al:LIPIcs.ICALP.2020.9,
  author =	{Bassilakis, Andrew and Drucker, Andrew and G\"{o}\"{o}s, Mika and Hu, Lunjia and Ma, Weiyun and Tan, Li-Yang},
  title =	{{The Power of Many Samples in Query Complexity}},
  booktitle =	{47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)},
  pages =	{9:1--9:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-138-2},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{168},
  editor =	{Czumaj, Artur and Dawar, Anuj and Merelli, Emanuela},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.9},
  URN =		{urn:nbn:de:0030-drops-124163},
  doi =		{10.4230/LIPIcs.ICALP.2020.9},
  annote =	{Keywords: Query complexity, Composition theorems}
}
Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2019.51
A Lower Bound for Sampling Disjoint Sets

Authors: Mika Göös and Thomas Watson

Published in: LIPIcs, Volume 145, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)

Abstract
Suppose Alice and Bob each start with private randomness and no other input, and they wish to engage in a protocol in which Alice ends up with a set x subseteq[n] and Bob ends up with a set y subseteq[n], such that (x,y) is uniformly distributed over all pairs of disjoint sets. We prove that for some constant beta<1, this requires Omega(n) communication even to get within statistical distance 1-beta^n of the target distribution. Previously, Ambainis, Schulman, Ta-Shma, Vazirani, and Wigderson (FOCS 1998) proved that Omega(sqrt{n}) communication is required to get within some constant statistical distance epsilon>0 of the uniform distribution over all pairs of disjoint sets of size sqrt{n}.
Cite as

Mika Göös and Thomas Watson. A Lower Bound for Sampling Disjoint Sets. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 51:1-51:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{goos_et_al:LIPIcs.APPROX-RANDOM.2019.51,
  author =	{G\"{o}\"{o}s, Mika and Watson, Thomas},
  title =	{{A Lower Bound for Sampling Disjoint Sets}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)},
  pages =	{51:1--51:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-125-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{145},
  editor =	{Achlioptas, Dimitris and V\'{e}gh, L\'{a}szl\'{o} A.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2019.51},
  URN =		{urn:nbn:de:0030-drops-112666},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2019.51},
  annote =	{Keywords: Communication complexity, set disjointness, sampling}
}
Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2019.56
String Matching: Communication, Circuits, and Learning

Authors: Alexander Golovnev, Mika Göös, Daniel Reichman, and Igor Shinkar

Published in: LIPIcs, Volume 145, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)

Abstract
String matching is the problem of deciding whether a given n-bit string contains a given k-bit pattern. We study the complexity of this problem in three settings. - Communication complexity. For small k, we provide near-optimal upper and lower bounds on the communication complexity of string matching. For large k, our bounds leave open an exponential gap; we exhibit some evidence for the existence of a better protocol. - Circuit complexity. We present several upper and lower bounds on the size of circuits with threshold and DeMorgan gates solving the string matching problem. Similarly to the above, our bounds are near-optimal for small k. - Learning. We consider the problem of learning a hidden pattern of length at most k relative to the classifier that assigns 1 to every string that contains the pattern. We prove optimal bounds on the VC dimension and sample complexity of this problem.
Cite as

Alexander Golovnev, Mika Göös, Daniel Reichman, and Igor Shinkar. String Matching: Communication, Circuits, and Learning. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 56:1-56:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{golovnev_et_al:LIPIcs.APPROX-RANDOM.2019.56,
  author =	{Golovnev, Alexander and G\"{o}\"{o}s, Mika and Reichman, Daniel and Shinkar, Igor},
  title =	{{String Matching: Communication, Circuits, and Learning}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)},
  pages =	{56:1--56:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-125-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{145},
  editor =	{Achlioptas, Dimitris and V\'{e}gh, L\'{a}szl\'{o} A.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2019.56},
  URN =		{urn:nbn:de:0030-drops-112717},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2019.56},
  annote =	{Keywords: string matching, communication complexity, circuit complexity, PAC learning}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2019.38
Adventures in Monotone Complexity and TFNP

Authors: Mika Göös, Pritish Kamath, Robert Robere, and Dmitry Sokolov

Published in: LIPIcs, Volume 124, 10th Innovations in Theoretical Computer Science Conference (ITCS 2019)

Abstract
Separations: We introduce a monotone variant of Xor-Sat and show it has exponential monotone circuit complexity. Since Xor-Sat is in NC^2, this improves qualitatively on the monotone vs. non-monotone separation of Tardos (1988). We also show that monotone span programs over R can be exponentially more powerful than over finite fields. These results can be interpreted as separating subclasses of TFNP in communication complexity. Characterizations: We show that the communication (resp. query) analogue of PPA (subclass of TFNP) captures span programs over F_2 (resp. Nullstellensatz degree over F_2). Previously, it was known that communication FP captures formulas (Karchmer - Wigderson, 1988) and that communication PLS captures circuits (Razborov, 1995).
Cite as

Mika Göös, Pritish Kamath, Robert Robere, and Dmitry Sokolov. Adventures in Monotone Complexity and TFNP. In 10th Innovations in Theoretical Computer Science Conference (ITCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 124, pp. 38:1-38:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{goos_et_al:LIPIcs.ITCS.2019.38,
  author =	{G\"{o}\"{o}s, Mika and Kamath, Pritish and Robere, Robert and Sokolov, Dmitry},
  title =	{{Adventures in Monotone Complexity and TFNP}},
  booktitle =	{10th Innovations in Theoretical Computer Science Conference (ITCS 2019)},
  pages =	{38:1--38:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-095-8},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{124},
  editor =	{Blum, Avrim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2019.38},
  URN =		{urn:nbn:de:0030-drops-101316},
  doi =		{10.4230/LIPIcs.ITCS.2019.38},
  annote =	{Keywords: TFNP, Monotone Complexity, Communication Complexity, Proof Complexity}
}
Document
DOI: 10.4230/LIPIcs.CCC.2018.23
A Tight Lower Bound for Entropy Flattening

Authors: Yi-Hsiu Chen, Mika Göös, Salil P. Vadhan, and Jiapeng Zhang

Published in: LIPIcs, Volume 102, 33rd Computational Complexity Conference (CCC 2018)

Abstract
We study entropy flattening: Given a circuit C_X implicitly describing an n-bit source X (namely, X is the output of C_X on a uniform random input), construct another circuit C_Y describing a source Y such that (1) source Y is nearly flat (uniform on its support), and (2) the Shannon entropy of Y is monotonically related to that of X. The standard solution is to have C_Y evaluate C_X altogether Theta(n^2) times on independent inputs and concatenate the results (correctness follows from the asymptotic equipartition property). In this paper, we show that this is optimal among black-box constructions: Any circuit C_Y for entropy flattening that repeatedly queries C_X as an oracle requires Omega(n^2) queries. Entropy flattening is a component used in the constructions of pseudorandom generators and other cryptographic primitives from one-way functions [Johan Håstad et al., 1999; John Rompel, 1990; Thomas Holenstein, 2006; Iftach Haitner et al., 2006; Iftach Haitner et al., 2009; Iftach Haitner et al., 2013; Iftach Haitner et al., 2010; Salil P. Vadhan and Colin Jia Zheng, 2012]. It is also used in reductions between problems complete for statistical zero-knowledge [Tatsuaki Okamoto, 2000; Amit Sahai and Salil P. Vadhan, 1997; Oded Goldreich et al., 1999; Vadhan, 1999]. The Theta(n^2) query complexity is often the main efficiency bottleneck. Our lower bound can be viewed as a step towards proving that the current best construction of pseudorandom generator from arbitrary one-way functions by Vadhan and Zheng (STOC 2012) has optimal efficiency.
Cite as

Yi-Hsiu Chen, Mika Göös, Salil P. Vadhan, and Jiapeng Zhang. A Tight Lower Bound for Entropy Flattening. In 33rd Computational Complexity Conference (CCC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 102, pp. 23:1-23:28, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{chen_et_al:LIPIcs.CCC.2018.23,
  author =	{Chen, Yi-Hsiu and G\"{o}\"{o}s, Mika and Vadhan, Salil P. and Zhang, Jiapeng},
  title =	{{A Tight Lower Bound for Entropy Flattening}},
  booktitle =	{33rd Computational Complexity Conference (CCC 2018)},
  pages =	{23:1--23:28},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-069-9},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{102},
  editor =	{Servedio, Rocco A.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2018.23},
  URN =		{urn:nbn:de:0030-drops-88669},
  doi =		{10.4230/LIPIcs.CCC.2018.23},
  annote =	{Keywords: Entropy, One-way function}
}
Document
DOI: 10.4230/LIPIcs.CCC.2017.12
Query-to-Communication Lifting for P^NP

Authors: Mika Göös, Pritish Kamath, Toniann Pitassi, and Thomas Watson

Published in: LIPIcs, Volume 79, 32nd Computational Complexity Conference (CCC 2017)

Abstract
We prove that the P^NP-type query complexity (alternatively, decision list width) of any boolean function f is quadratically related to the P^NP-type communication complexity of a lifted version of f. As an application, we show that a certain "product" lower bound method of Impagliazzo and Williams (CCC 2010) fails to capture P^NP communication complexity up to polynomial factors, which answers a question of Papakonstantinou, Scheder, and Song (CCC 2014).
Cite as

Mika Göös, Pritish Kamath, Toniann Pitassi, and Thomas Watson. Query-to-Communication Lifting for P^NP. In 32nd Computational Complexity Conference (CCC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 79, pp. 12:1-12:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{goos_et_al:LIPIcs.CCC.2017.12,
  author =	{G\"{o}\"{o}s, Mika and Kamath, Pritish and Pitassi, Toniann and Watson, Thomas},
  title =	{{Query-to-Communication Lifting for P^NP}},
  booktitle =	{32nd Computational Complexity Conference (CCC 2017)},
  pages =	{12:1--12:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-040-8},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{79},
  editor =	{O'Donnell, Ryan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2017.12},
  URN =		{urn:nbn:de:0030-drops-75388},
  doi =		{10.4230/LIPIcs.CCC.2017.12},
  annote =	{Keywords: Communication Complexity, Query Complexity, Lifting Theorem, P^NP}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2017.52
Randomized Communication vs. Partition Number

Authors: Mika Göös, T. S. Jayram, Toniann Pitassi, and Thomas Watson

Published in: LIPIcs, Volume 80, 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)

Abstract
We show that randomized communication complexity can be superlogarithmic in the partition number of the associated communication matrix, and we obtain near-optimal randomized lower bounds for the Clique vs. Independent Set problem. These results strengthen the deterministic lower bounds obtained in prior work (Goos, Pitassi, and Watson, FOCS 2015). One of our main technical contributions states that information complexity when the cost is measured with respect to only 1-inputs (or only 0-inputs) is essentially equivalent to information complexity with respect to all inputs.
Cite as

Mika Göös, T. S. Jayram, Toniann Pitassi, and Thomas Watson. Randomized Communication vs. Partition Number. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 52:1-52:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{goos_et_al:LIPIcs.ICALP.2017.52,
  author =	{G\"{o}\"{o}s, Mika and Jayram, T. S. and Pitassi, Toniann and Watson, Thomas},
  title =	{{Randomized Communication vs. Partition Number}},
  booktitle =	{44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)},
  pages =	{52:1--52:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-041-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{80},
  editor =	{Chatzigiannakis, Ioannis and Indyk, Piotr and Kuhn, Fabian and Muscholl, Anca},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2017.52},
  URN =		{urn:nbn:de:0030-drops-74861},
  doi =		{10.4230/LIPIcs.ICALP.2017.52},
  annote =	{Keywords: communication complexity, partition number, information complexity}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2016.86
The Landscape of Communication Complexity Classes

Authors: Mika Göös, Toniann Pitassi, and Thomas Watson

Published in: LIPIcs, Volume 55, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)

Abstract
We prove several results which, together with prior work, provide a nearly-complete picture of the relationships among classical communication complexity classes between P and PSPACE, short of proving lower bounds against classes for which no explicit lower bounds were already known. Our article also serves as an up-to-date survey on the state of structural communication complexity. Among our new results we show that MA !subseteq ZPP^{NP[1]}, that is, Merlin–Arthur proof systems cannot be simulated by zero-sided error randomized protocols with one NP query. Here the class ZPP^{NP[1]} has the property that generalizing it in the slightest ways would make it contain AM intersect coAM, for which it is notoriously open to prove any explicit lower bounds. We also prove that US !subseteq ZPP^{NP[1]}, where US is the class whose canonically complete problem is the variant of set-disjointness where yes-instances are uniquely intersecting. We also prove that US !subseteq coDP, where DP is the class of differences of two NP sets. Finally, we explore an intriguing open issue: are rank-1 matrices inherently more powerful than rectangles in communication complexity? We prove a new separation concerning PP that sheds light on this issue and strengthens some previously known separations.
Cite as

Mika Göös, Toniann Pitassi, and Thomas Watson. The Landscape of Communication Complexity Classes. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 86:1-86:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{goos_et_al:LIPIcs.ICALP.2016.86,
  author =	{G\"{o}\"{o}s, Mika and Pitassi, Toniann and Watson, Thomas},
  title =	{{The Landscape of Communication Complexity Classes}},
  booktitle =	{43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)},
  pages =	{86:1--86:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-013-2},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{55},
  editor =	{Chatzigiannakis, Ioannis and Mitzenmacher, Michael and Rabani, Yuval and Sangiorgi, Davide},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2016.86},
  URN =		{urn:nbn:de:0030-drops-61990},
  doi =		{10.4230/LIPIcs.ICALP.2016.86},
  annote =	{Keywords: Landscape, communication, complexity, classes}
}
Document
DOI: 10.4230/LIPIcs.CCC.2016.5
A Composition Theorem for Conical Juntas

Authors: Mika Göös and T. S. Jayram

Published in: LIPIcs, Volume 50, 31st Conference on Computational Complexity (CCC 2016)

Abstract
We describe a general method of proving degree lower bounds for conical juntas (nonnegative combinations of conjunctions) that compute recursively defined boolean functions. Such lower bounds are known to carry over to communication complexity. We give two applications: - AND-OR trees. We show a near-optimal ~Omega(n^{0.753...}) randomised communication lower bound for the recursive NAND function (a.k.a. AND-OR tree). This answers an open question posed by Beame and Lawry. - Majority trees. We show an Omega(2.59^k) randomised communication lower bound for the 3-majority tree of height k. This improves over the state-of-the-art already in the context of randomised decision tree complexity.
Cite as

Mika Göös and T. S. Jayram. A Composition Theorem for Conical Juntas. In 31st Conference on Computational Complexity (CCC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 50, pp. 5:1-5:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{goos_et_al:LIPIcs.CCC.2016.5,
  author =	{G\"{o}\"{o}s, Mika and Jayram, T. S.},
  title =	{{A Composition Theorem for Conical Juntas}},
  booktitle =	{31st Conference on Computational Complexity (CCC 2016)},
  pages =	{5:1--5:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-008-8},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{50},
  editor =	{Raz, Ran},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2016.5},
  URN =		{urn:nbn:de:0030-drops-58497},
  doi =		{10.4230/LIPIcs.CCC.2016.5},
  annote =	{Keywords: Composition theorems, conical juntas}
}
Document
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2014.721
Communication Complexity of Set-Disjointness for All Probabilities

Authors: Mika Göös and Thomas Watson

Published in: LIPIcs, Volume 28, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)

Abstract
We study set-disjointness in a generalized model of randomized two-party communication where the probability of acceptance must be at least alpha(n) on yes-inputs and at most beta(n) on no-inputs, for some functions alpha(n)>beta(n). Our main result is a complete characterization of the private-coin communication complexity of set-disjointness for all functions alpha and beta, and a near-complete characterization for public-coin protocols. In particular, we obtain a simple proof of a theorem of Braverman and Moitra (STOC 2013), who studied the case where alpha=1/2+epsilon(n) and beta=1/2-epsilon(n). The following contributions play a crucial role in our characterization and are interesting in their own right. (1) We introduce two communication analogues of the classical complexity class that captures small bounded-error computations: we define a "restricted" class SBP (which lies between MA and AM) and an "unrestricted" class USBP. The distinction between them is analogous to the distinction between the well-known communication classes PP and UPP. (2) We show that the SBP communication complexity is precisely captured by the classical corruption lower bound method. This sharpens a theorem of Klauck (CCC 2003). (3) We use information complexity arguments to prove a linear lower bound on the USBP complexity of set-disjointness.
Cite as

Mika Göös and Thomas Watson. Communication Complexity of Set-Disjointness for All Probabilities. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 28, pp. 721-736, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{goos_et_al:LIPIcs.APPROX-RANDOM.2014.721,
  author =	{G\"{o}\"{o}s, Mika and Watson, Thomas},
  title =	{{Communication Complexity of Set-Disjointness for All Probabilities}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)},
  pages =	{721--736},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-74-3},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{28},
  editor =	{Jansen, Klaus and Rolim, Jos\'{e} and Devanur, Nikhil R. and Moore, Cristopher},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2014.721},
  URN =		{urn:nbn:de:0030-drops-47342},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2014.721},
  annote =	{Keywords: Communication Complexity, Set-Disjointness, All Probabilities}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact